package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: CGF
 * @CreateTime: 2021/12/22 16:34
 * @Description:
 */
public class Solution105 {
    Map<Integer, Integer> map = null;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        map = new HashMap();
        for (int i=0; i<len; i++){
            map.put(inorder[i], i);
        }
        return helper(preorder, inorder, 0, len-1,0, len-1);
    }

    TreeNode helper(int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight){
        if (preLeft > preRight) return null;
        int inRoot = map.get(preorder[preLeft]);
        TreeNode root = new TreeNode(preorder[preLeft]);
        // 计算左节点长度
        int leftLong = inRoot - inLeft;

        root.left = helper(preorder, inorder, preLeft+1, preLeft+leftLong, inLeft, inRoot-1);
        root.right = helper(preorder, inorder,  preLeft+leftLong+1, preRight, inRoot+1, inRight);
        return root;
    }
}
